﻿using System;
using System.Text;
using System.Linq;
using System.Collections.Generic;
using Algoritmia.Utils.Backtracers;

namespace Algoritmia.Problems.TextProcessing
{
    public class ParagraphFormatter
    {
        private readonly Func<int, int, int> _penaltyFunction;
        private readonly Func<IEnumerable<KeyValuePair<int, int>>, IBacktracer<int, int>> _createBacktracer;

        public ParagraphFormatter(Func<int,int,int> penaltyFunction = null,Func<IEnumerable<KeyValuePair<int,int>>,IBacktracer<int, int>> createBacktracer = null)
        {
            _penaltyFunction = penaltyFunction ?? ((c, L) => c <= L ? (L - c)*(L-c)*(L-c) : int.MaxValue);
            _createBacktracer = createBacktracer ?? (bp => new DynamicBacktracer<int, int>(bp));
        }

        public int Penalty(DataStructures.Lists.IList<string> words, int columns)
        {
            var P = new int[words.Count + 1];
            for(int j = 1; j <= words.Count; j++)
            {
                int chars = words[j - 1].Length;
                P[j] = P[j - 1] + _penaltyFunction(chars, columns);
                for(int i = j-2; i >= 0; i--)
                {
                    chars += words[i].Length;
                    if (chars + j - i - 1 > columns) break;
                    P[j] = Math.Min(P[j], P[i] + _penaltyFunction(chars + j - i - 1, columns));
                }
            }
            return P[words.Count];
        }

        public string Justify(DataStructures.Lists.IList<string> words, int columns)
        {
            var P = new int[words.Count + 1];
            var back = new int[words.Count + 1];
            for (int j = 1; j <= words.Count; j++)
            {
                int chars = words[j - 1].Length;
                P[j] = P[j - 1] + _penaltyFunction(chars, columns);
                back[j] = j - 1;
                for (int i = j - 2; i >= 0; i--)
                {
                    chars += words[i].Length;
                    if (chars + j - i - 1 > columns) break;
                    var r = P[i] + _penaltyFunction(chars + j - i - 1, columns);
                    if ( r < P[j] )
                    {
                        P[j] = r;
                        back[j] = i;
                    }
                }
            }
            var par = _createBacktracer(back.Select((e, i) => new KeyValuePair<int, int>(i, e))).Backtrace(words.Count);
            par.InsertAt(0,0);

            var sb = new StringBuilder();

            for(int i = 0; i < par.Count-1;i++)
            {
                var lineChars =
                    words.Where((e, index) => index >= par[i] && index < par[i + 1]).Select(w => w.Length).Sum();
                var blanks = columns - lineChars;
                int separation = 0, extra = 0;
                bool onlyOneWord = false;
                if ( par[i+1] - par[i] > 1)
                {
                    separation = blanks/(par[i + 1] - par[i] - 1);
                    extra = blanks % (par[i + 1] - par[i] - 1);
                }
                else
                {
                    onlyOneWord = true;
                }

                if (onlyOneWord)
                {
                    sb.Append(words[par[i]]);
                    sb.Append(new string(' ', columns - words[par[i]].Length));
                }
                else
                {
                    int limit = par[i];
                    string spaces;
                    if (extra > 0)
                    {
                        spaces = new string(' ', separation + 1);
                        sb.Append(string.Join(spaces, words.Where((e, index) => index < par[i] + extra && index >= par[i])));
                        sb.Append(spaces);
                        limit += extra;
                    }
                    spaces = new string(' ', separation);
                    sb.Append(string.Join(spaces, words.Where((e, index) => index >= limit && index < par[i + 1])));
                }
              
                sb.Append("\r\n");
            }
            return sb.ToString();
        }
    }
}
